#include <assert.h>
#include <mem.h>
#include <string.h>
#include "list_arr.h"

void _lta_enlarge( list_arr* _lt );

list_arr* lta_create()
{
    list_arr *_lt;
    _lt = (list_arr *) palloc( sizeof(list_arr) );
    assert( _lt != NULL );

    _lt->bound = LIST_ARRAY_SIZE;
    _lt->val = (void***) palloc( sizeof(void**) * (_lt->bound/LIST_ARRAY_SIZE) );
    assert( _lt->val != NULL );
    
    _lt->val[0] = (void**) palloc( sizeof(void*) * LIST_ARRAY_SIZE );
    assert( _lt->val[0] != NULL );

    _lt->size = 0;
    _lt->bsorted = 0;

    return _lt;
}

void lta_destroy( list_arr* _lt )
{
    int i;
    for( i = 0; i < _lt->bound / LIST_ARRAY_SIZE; ++i )
    {
        pfree( _lt->val[0] );
    }
    pfree( _lt->val );
    pfree( _lt );
}

int32 lta_size( list_arr* _lt )
{
    return _lt->size;
}

void lta_pushb( list_arr* _lt, void* _val )
{
    int row = _lt->size / LIST_ARRAY_SIZE;
    int col = _lt->size % LIST_ARRAY_SIZE;
	if( _lt->size >= _lt->bound )
		_lta_enlarge( _lt );
	_lt->val[row][col] = _val;
	++_lt->size;
}

void lta_pushf( list_arr *_lt, void *_val )
{
	int i;
	int row = _lt->size / LIST_ARRAY_SIZE;
	int col = _lt->size % LIST_ARRAY_SIZE;
	if( _lt->size >= _lt->bound )
		_lta_enlarge( _lt );
	memmove( _lt->val[row]+1, _lt->val[row], LIST_ARRAY_SIZE-1 );
	for( i = row; i > 0; --i )
	{
		_lt->val[i][0] = _lt->val[i-1][LIST_ARRAY_SIZE-1];
		memmove( _lt->val[i-1]+1, _lt->val[i-1], LIST_ARRAY_SIZE-1 );
	}
	_lt->val[0][0] = _val;
	++_lt->size;
}

lta_iterator lta_insert( list_arr *_lt, lta_iterator _it, void *_val )
{
	return lta_insertp( _lt, _it, _val );
}

lta_iterator lta_insertp( list_arr *_lt, int32 _pos, void *_val )
{
	if( _pos <= 0 )
	{
		lta_pushf( _lt, _val );
		return 0;
	}
	else if( _pos >= lta_size( _lt ) )
	{
		lta_pushb( _lt, _val );
		return lta_end(_lt)-1;
	}
	else
	{
		int i;
		int row = _lt->size / LIST_ARRAY_SIZE;
		int col = _lt->size % LIST_ARRAY_SIZE;
		int rown = _pos / LIST_ARRAY_SIZE;
		int coln = _pos / LIST_ARRAY_SIZE;
		if( _lt->size >= _lt->bound )
			_lta_enlarge( _lt );
		if( rown < row )
		{
			memmove( _lt->val[row]+1, _lt->val[row], LIST_ARRAY_SIZE-1 );
			for( i = row; i > rown+1; --i )
			{
				_lt->val[i][0] = _lt->val[i-1][LIST_ARRAY_SIZE-1];
				memmove( _lt->val[i-1]+1, _lt->val[i-1], LIST_ARRAY_SIZE-1 );
			}
			_lt->val[i][0] = _lt->val[i-1][LIST_ARRAY_SIZE-1];
			memmove( _lt->val[i-1]+coln+1, _lt->val[i-1]+coln, LIST_ARRAY_SIZE-coln-1 );
		}
		else
			memmove( _lt->val[row]+col+1, _lt->val[row]+col, LIST_ARRAY_SIZE-col-1 );
		
		_lt->val[rown][coln] = _val;
		++_lt->size;
		return _pos;
	}
}

void* lta_val( lta_iterator _it )
{
	return NULL;
}

void* lta_get( list_arr *_lt, int32 _pos )
{
	int row = _pos / LIST_ARRAY_SIZE;
	int col = _pos % LIST_ARRAY_SIZE;
	return _lt->val[row][col];
}

void* lta_front( list_arr *_lt )
{
	return _lt->val[0][0];
}

void* lta_back( list_arr *_lt )
{
	return lta_get( _lt, lta_size(_lt)-1 );
}

lta_iterator lta_begin( list_arr *_lt )
{
	return 0;
}

lta_iterator lta_end( list_arr *_lt )
{
	return lta_size( _lt );
}

lta_iterator lta_next( lta_iterator _it )
{
	return _it+1;
}

lta_iterator lta_pre( lta_iterator _it )
{
	return _it-1;
}

lta_iterator lta_find( list_arr *_lt, void *_key, compare _fun )
{
	lta_iterator _val = lta_end(_lt);
	if( _lt->bsorted )
	{
		int c;
		int low = 0, high = lta_size(_lt)-1, mid;
		while( low <= high )
		{
			mid = (low+high)/2;
			c = _fun( lta_get(_lt,mid), _key );
			if( c == 0 )
			{
				_val = mid;
				break;
			}
			else if( c < 0 )
				low = mid+1;
			else
				high = mid-1;
		}
	}
	else
	{
		int i;
		for( i = 0; i < lta_size(_lt); ++i )
		{
			if( 0 == _fun( lta_get(_lt,i), _key ) )
			{
				_val = i;
				break;
			}
		}
	}
	return _val;
}

// the following functions will delete data from list
// {3 delete begin

/// list pop front
void* lta_popf( list_arr* _lt );
/// list pop back
void* lta_popb( list_arr *_lt );
/// remove the iterator( and it's data from list )
/// return the data
void* lta_remove( list_arr *_lt, lta_iterator _it );
/// remove the pos-th data from the list
/// return the data
void* lta_removep( list_arr *_lt, int32 _pos );

// delete finished 3}

// sort ascend the list.
void lta_sort( list_arr *_lt, compare _fun );
